// BalancedPatition.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

/*
Balanced Partition. You have a set of n integers each in the range 0 ... K. 
Partition these integers into two subsets such that you minimize |S1 - S2|, 
where S1 and S2 denote the sums of the elements in each of the two subsets. 

the link is item 7 http://people.csail.mit.edu/bdean/6.046/dp/

Algorithm:
define P(i,j), i indicates the items in the set, j indicates the sum of one or
more items in the set.

P(i,j) = 1 iff there exists items in the set (defined by i) whose sum is equal to j;
P(i,j) = 0 otherwise

the recusive formula:
P(i,j) = 1 if P(i-1, j)==1 or P(i-1, j-V(i)) == 1 (V(i) is the value for item i)
P(i,j) = 0 otherwise

A follow up question: what if 2n numbers are provided, devide the set to be two set, 
each contains n numbers with the minimum sum differnece?
*/

#define MAX(x, y)	(x>y?x:y)

#define COUNT 9
#define MAX_SUM	500
int P[COUNT+1][MAX_SUM+1]={0};

int Partition( int *Array, int Count)
{
	int sum=0;
	int i, j;

	for( i =0; i<Count; i++ )
	{
		sum+=Array[i];
	}
	
	if( sum > MAX_SUM)
	{
		cout<<"invalid input"<<endl;
		return -1;
	}

	//
	// Construct DP table
	//
	P[0][0] = 1;

	// Note: i starts from 1
	for( i=1; i<=Count; i++ )
	{
		for( j=0; j<=sum/2+1; j++)
		{
			P[i][j] = P[i-1][j];
			if( j>=Array[i-1] )
			{
				P[i][j] = MAX(P[i][j], P[i-1][j-Array[i-1]]);
			}
		}
	}

	for( j = sum/2; j>0; j--)
	{
		if( P[Count][j] != 0 )
		{
			//
			// Find the largest value less than sum/2
			//
			break;
		}
	}
	
	int min = sum-2*j;

	//
	// print the set by reservse tracking. 
	// this part can be ignored if the path is not required
	//
	cout<<"One subset is: ";
	for( i=Count; i>=0; i-- )
	{
		if(P[i][j] == 0)
		{
			cout<<Array[i]<<" ";
			if(j-Array[i]>=0)
				j=j-Array[i];
			else
				break;
		}
	}
	cout<<"with the minimum difference value "<<min<<endl;
	
	return min;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int Array[COUNT] = {19, 3, 6, 21, 5, 20, 7, 11, 15};

	cout<<"The data set is: ";
	for( int i=0; i<COUNT; i++ )
	{
		cout<<Array[i]<<" ";
	}
	cout<<endl;

	Partition( Array, COUNT );

	cout<<"Press any key to terminate..."<<endl;	
	return getchar();;
}

